package 代码随想录_动态规划.完全背包;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author zx
 * @create 2023-02-02 23:30
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
 * 2.确定递推公式
 *  如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
 *  所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
 * 3.dp数组如何初始化
 *  从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，
 *  否则递归下去后面都都是false了。
 *  下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
 * 4.确定遍历顺序
 *  遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。
 * 5.举例推导dp数组
 */
public class 单词拆分_139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1;i <= s.length();i++){
            for(int j = 0;j < i;j++){
                if(dp[j] == true && set.contains(s.substring(j,i))){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
